import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/7/30.
 * 给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。

 如果没有两个连续的 1，返回 0 。
 */
public class BinaryGap {

    public static void main(String[] args) {
        System.out.println(new BinaryGap().binaryGap(22));
        System.out.println(new BinaryGap().binaryGap(5));
        System.out.println(new BinaryGap().binaryGap(6));
        System.out.println(new BinaryGap().binaryGap(8));
    }

    public int binaryGap(int N) {
        List<Integer> onePositions = new ArrayList<>();
        int mask = 0x1;
        int position = 0;
        while ((mask | 0x0) != 0) {
            if ((N & mask) != 0) {
                // 找到一个1
                onePositions.add(position);
            }
            position++;
            mask <<= 1;
        }

        if (onePositions.size() <= 1) {
            return 0;
        }

        int maxGap = 0;
        for (int index = 0; index < onePositions.size() - 1; index++) {
            maxGap = Math.max(maxGap, onePositions.get(index + 1) - onePositions.get(index));
        }

        return maxGap;
    }
}
